//https://leetcode.cn/problems/remove-zero-sum-consecutive-nodes-from-linked-list/

class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {
        int i = 0, j = 0;
        ListNode* pphead = (ListNode*)malloc(sizeof(ListNode));
        vector<int> temp;
        pphead->next = head;
        if (pphead->next == NULL)
        {
            return pphead->next;
        }

        ListNode* cur = head;
        ListNode* prev = pphead;
        //前缀和为0
        int sum = 0;
        while (cur)
        {
            sum += cur->val;
            temp.push_back(sum);  //1 3 6 3 7
            if (sum == 0)
            {
                pphead->next = cur->next;
                removeZeroSumSublists(pphead->next);
            }
            cur = cur->next;
        }
        bool e = false;
        for (; i < temp.size() - 1; i++)
        {
            for (j = i + 1; j < temp.size(); j++)
            {
                if (temp[i] == temp[j])
                {
                    e = true;
                    break;
                }
            }
            if (e)
            {
                break;
            }
        }
        //没找到
        if (!e)
        {
            return pphead->next;
        }

        int gap = j - i;

        cur = head;
        while (i-- && cur)
        {
            cur = cur->next;
        }

        while (gap-- && cur)
        {
            ListNode* p = cur->next;
            cur->next = p->next;
        }

        return removeZeroSumSublists(pphead->next);

    }
};

